package com.njupt.StackAndQueue;

import org.aspectj.apache.bcel.classfile.InnerClass;

import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/16 21:21
 * @Description:347. 前 K 个高频元素
 * @Version: 1.0
 */


public class TopKFrequent {

    /**
     * map转成EntrySet放入集合中进行排毒
     * @param nums
     * @param k
     * @return
     */
    public static  int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i],0) +1 );
        }
        List<Map.Entry<Integer, Integer>>
                entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries,(e1,e2)->{
            return e2.getValue() - e1.getValue();
        });
        Iterator<Map.Entry<Integer, Integer>> iterator = entries.iterator();
        int index = 0;
        while(iterator.hasNext()){

            result[index++] = iterator.next().getKey();
            if(index == k){
                return result;
            }
        }
        return result;
    }

    /**
     * 采用优先级队列
     * @param nums
     * @param k
     * @return
     */
    public static  int[] topKFrequent1(int[] nums, int k){
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((item1,item2)->{
            return item2[1] - item1[1];
        });

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }

       for(Map.Entry<Integer,Integer> entry:map.entrySet()){
           pq.add(new int[]{entry.getKey(),entry.getValue()});
       }

       int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.poll()[0];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int[] ints = TopKFrequent.topKFrequent1(nums, 2);
        System.out.println(Arrays.toString(ints));
    }
}
